import java.util.Random;

public class demo1 {
    public int[] sortArray(int[] nums){
        kuai(nums,0,nums.length-1);
        return nums;
    }
    public void kuai(int[] nums,int l,int r){
        if(l>=r)return;
        int key=nums[new Random().nextInt()];
        int left=l-1,right=r+1,i=l;
        while(i<r){
            if(nums[i]<key)swap(nums,++left,i++);
            else if(nums[i]==key)i++;
            else swap(nums,--right,i);
        }
        kuai(nums,l,left);
        kuai(nums,right,r);
    }
    public void swap(int[] nums,int x,int y){
        int temp=nums[x];
        nums[x]=nums[y];
        nums[y]=temp;
    }
}
